package LinkList;

/*
删除链表的倒数第N个节点
给你一个链表，删除链表的倒数第n个结点，并且返回链表的头结点。
示例 1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
示例 2：
输入：head = [1], n = 1
输出：[]
示例 3：
输入：head = [1,2], n = 1
输出：[1]
作者：LeetCode
链接：https://leetcode.cn/leetbook/read/linked-list/jf1cc/
 */

import java.util.Deque;
import java.util.LinkedList;

public class _24删除链表的倒数第N个节点 {
    public static void main(String[] args) {

    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }


    public ListNode removeNthFromEnd(ListNode head, int n) {

        int count = 0;
        ListNode cur = head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        //倘若没有哑结点，则必须对删除头结点这一特殊情况进行判断
        if(count == n){
            head = head.next;
            return head;
        }
        ListNode res = head;

        while (count - n - 1 > 0) {
            head = head.next;
            count--;
        }
        head.next = head.next.next;
        return res;

    }

    //官解:方法一暴力哑结点解法
    //在对链表进行操作时，一种常用的技巧是添加一个哑节点（dummy node），它的 next 指针指向链表的头节点。这样一来，我们就不需要对头节点进行特殊的判断了。
//    class Solution {
//        public ListNode removeNthFromEnd(ListNode head, int n) {
//            ListNode dummy = new ListNode(0, head);
//            int length = getLength(head);
//            ListNode cur = dummy;
//            for (int i = 1; i < length - n + 1; ++i) {
//                cur = cur.next;
//            }
//            cur.next = cur.next.next;
//            ListNode ans = dummy.next;
//            return ans;
//        }
//
//        public int getLength(ListNode head) {
//            int length = 0;
//            while (head != null) {
//                ++length;
//                head = head.next;
//            }
//            return length;
//        }
//    }

    //方法二：快慢双指针
    //核心思路是人为制造参差n，这样快指针到达链表的末尾时慢指针正好为我们需要删除的结点

    //由于我们需要找到倒数第 n 个节点，因此我们可以使用两个指针 first 和 second 同时对链表进行遍历，并且 first 比 second 超前 n 个节点。
    //当 first 遍历到链表的末尾时，second 就恰好处于倒数第 n 个节点。


//    class Solution {
//        public ListNode removeNthFromEnd(ListNode head, int n) {
//            ListNode dummy = new ListNode(0, head);
//            ListNode first = head;
//            ListNode second = dummy;
//            for (int i = 0; i < n; ++i) {
//                first = first.next;
//            }
//            while (first != null) {
//                first = first.next;
//                second = second.next;
//            }
//            second.next = second.next.next;
//            ListNode ans = dummy.next;
//            return ans;
//        }
//    }




}
